#include<iostream>
using namespace std;

long long GCD(long long a,long long b){
    for(long long c = a % b; c; c = a % b){
        a = b;
        b = c;
    }
    return b;
}

int main(){
    int T;
    
    for(cin >> T; T; T--){
        long long a, b;
        
        cin >> a >> b;
        for(long long c = GCD(a, b);c != 1;c = GCD(a, b)){
            b /= c;
        }
        cout << (b == 1 ? -1 : b) << endl; 
    }
    return 0;
}
